// 公共头文件【中枢，将三层Cache联系起来】
#include <iostream>
#include <vector>
#include <assert.h>
#include <thread>
#include <mutex>
#include <time.h>
#include <algorithm>
#include <unordered_map>

#include "objectPool.hpp"

#define Page_Shift 13   // 页大小转换偏移，我们这里以页的大小为8KB(8192字节)为例，PAGE_SHIFT的值就是13

// 根据对齐规则 ThreadCache ：自由链表(桶)的个数是 208 个，且允许申请的最大字节数为 256KB 
static const size_t ThreadCache_Max_Bytes = 256*1024;
static const size_t ThreadCache_FreeLists = 208;
static const size_t CentralCache_SpanLists = 208;
static const size_t PageCache_PageLists = 129;

// CentralCache ,一个页的大小一般为 4KB 或者 8KB，以 8KB 为例，根据进程地址空间，当32位机器下 2^32 / 2^13 = 2^19; 64位机器下 进程地址空间被分为 2^64 / 2^13 = 2^51 个页。那么多个页，肯定要被管理起来 -> 也就需要有页号的概念
//               [页号本质与地址没有太大的差别，：地址是以一个字节一个单位， 页是以多个字节一个单位]
#ifdef _WIN64
    #include <Windows.h>
    typedef unsigned long long Page_Id;
#elif _WIN32
    #include <Windows.h>
    typedef size_t Page_Id;
#else
    // Linux
    typedef unsigned long long Page_Id;
#endif


// 直接将内存返还给 堆
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // linux下为brk, mmap等
    // ...
#endif
}

class Util
{
public:
    // 内存链表：将头指针 指向下一个节点
    static void*& nextObj(void* ptr)
    {
        return (*(void**)ptr);
    }
};


// ThreadCache 的自由链表的结构
// 管理已经切分好的 小对象 的自由链表
class FreeList
{
private:
    void* free_list = nullptr;      // 自由链表
    size_t max_obj = 1;     // 往 CentralCache 中申请的初始值先设为1

    size_t count_obj = 0;   // 当前链表中的对象数量 
public:
    // 在一个自由链表中，必含有 插入和删除内存对象节点的操作【头插 and 头删】
    void pushObjToList(void* obj)
    {
        assert(obj);
        // 头插
        Util::nextObj(obj) = free_list;
        free_list = obj;
    }
    // 插入一定范围的 obj 内存对象
    void pushRangeObj(void* start, void* end, size_t count_obj_add)
    {
        assert(start);
        assert(end);
        // 开始头插
        Util::nextObj(end) = free_list;
        free_list = start;
        count_obj += count_obj_add;
    }
    void* popObjFromList()
    {
        assert(free_list);

        // 头删
        void* obj = free_list;
        free_list = Util::nextObj(free_list);
        return obj;
    }
    // 删除一定范围的 obj 内存对象
    void popRangeObj(void*& start, void*& end, size_t n)
    {
        assert(n <= count_obj);
        assert(start);
        assert(end);
        // 头删
        start = free_list;
        end = start;
        for(size_t i = 0; i < n; i++)
        {
            end = Util::nextObj(end);
        }
        free_list = Util::nextObj(end);
        Util::nextObj(end) = nullptr; // 断开连接
        count_obj -= n;
    }
    // 判断是否为空
    bool isEmptyList()
    {
        return free_list==nullptr;
    }
    // 获取申请对象数量的数值
    size_t& getMaxObj()
    {
        return max_obj;
    }
    // 获取当前链表中的对象数量
    size_t getObjNum()
    {
        return count_obj;
    }
};

// 负责管理自由链表 存储的内存块大小的 对齐和映射关系【根据不同大小的内存对象块映射到不同的自由链表中】
class ObjFreelist_AlignMap
{
private:
    static inline size_t _roundUp(size_t bytes, size_t alignNum)
    {
        size_t alignSize = 0;
        if(bytes%alignNum != 0){
            alignSize = (bytes / alignNum + 1)*alignNum;
        }
        else{
            alignSize = bytes;
        }
        return alignSize;
    }
    static inline size_t _hashIndex(size_t bytes, size_t alignNum)
    {
        size_t index = 0;
        if(bytes%alignNum != 0){
            index = bytes / alignNum;
        }
        else{
            index = bytes / alignNum + 1;
        }
        return index;
    }
public:
    // 获取向上对齐后的字节数
    static inline size_t roundUp(size_t bytes)
    {
        if(bytes <= 128){
            return _roundUp(bytes, 0);
        }
        else if(bytes <= 1024){
            return _roundUp(bytes, 16);
        }
        else if(bytes <= 8*1024){
            return _roundUp(bytes, 128);
        }
        else if(bytes <= 64*1024){
            return _roundUp(bytes, 1024);
        }
        else if(bytes <= 256*1024){
            return _roundUp(bytes, 8*1024);
        }
        else{
            // 大于 256KB 的按页对齐
            return _roundUp(bytes, 1 << Page_Shift);

            // assert(false);
            // return -1;
        }
    }
    // 获取对应哈希桶的下标
    static inline size_t hashIndex(size_t bytes)
    {
        static size_t freelistGroup[4] = {16, 56, 56, 56};  // 代表每个区间有多少个自由链表
        if(bytes <= 128){
            return _hashIndex(bytes, 3);
        }
        else if(bytes <= 1024){
            return _hashIndex(bytes-128, 4) + freelistGroup[0];
        }
        else if(bytes <= 8*1024){
            return _hashIndex(bytes-1024, 7) + freelistGroup[0] + freelistGroup[1];
        }
        else if(bytes <= 64*1024){
            return _hashIndex(bytes-8*1024, 10) + freelistGroup[0] + freelistGroup[1] + freelistGroup[2];
        }
        else if(bytes <= 256*1024){
            return _hashIndex(bytes-64*1024, 13) + freelistGroup[0] + freelistGroup[1] + freelistGroup[2] + freelistGroup[3];
        }
        else{
            assert(false);
            return -1;
        }
    }

    // CentralCache 层的 满反馈调节算法[threadCache 层一次 从 centralCache 获取对象的上限]
    static size_t getMaxObjFromCentralCache(size_t bytes)
    {
        assert(bytes > 0);

        // 对象越小，计算出的上限越高
        // 对象越大，计算出的上限越低
        int num = ThreadCache_Max_Bytes / bytes;
        if(num < 2) num = 2;        // 最小值
        if(num > 512) num = 512;    // 最大值
        return num;
    }

    // CentralCache 层若为空，需要向 PageCache 层申请内存块(单位为 页)
    static size_t allocaPageFromPageCache(size_t alignSize)
    {
        size_t num = getMaxObjFromCentralCache(alignSize);
        size_t get_all_size = num * alignSize;  // num 个 alignSize 大小的对象所需要的字节数
        size_t npage = get_all_size >> Page_Shift;
        if(npage == 0)
            npage = 1;  // 至少给 1 页
        return npage;
    }

};


// CentralCache 的span 结构
struct Span
{
    Page_Id page_id = 0;    // 大块内存起始的 页的编号
    size_t n = 0;           // 管理的页的数量
    Span* next = nullptr;   // 双链表结构——Span的前一个结点
    Span* prev = nullptr;   // Span的后一个结点
    
    size_t use_count = 0;   // 切好的小块内存，分配给 threadCache 的计数
    void* span_freelist = nullptr;  // 切好的小块内存的自由链表

    bool isUse = false; // 代表该 span 是否被使用
    size_t objSize = 0; // 代表该 span 中小块内存的大小
};
class SpanList
{
private:
    Span* spanlist_head;

    // 内存池
    static objectPool<Span> spanlist_pool;
public:
    std::mutex mtx; // 加桶锁
public:
    SpanList()
    {
        // spanlist_head = new Span;
        spanlist_head = spanlist_pool.New(); // 从内存池中申请一个 Span
        spanlist_head->next = spanlist_head;
        spanlist_head->prev = spanlist_head;
    }
    // 在 pos 位置插入一个 span 对象
    void insertSpanInPos(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);
        Span* prev = pos->prev;

        prev->next = newSpan;
        newSpan->prev = prev;
        newSpan->next = pos;
        pos->prev = newSpan;
    }
    // 删除 pos 位置的 Span 对象
    void eraseSpanInPos(Span* pos)
    {
        assert(pos);
        assert(pos != spanlist_head);

        Span* prev = pos->prev;
        Span* next = pos->next;
        prev->next = next;
        next->prev = prev;
        // !!! 注意：不能给 pos 位置的这个 span 对象 delete
    }
    // 迭代器：begin
    Span* slistBegin()
    {
        return spanlist_head->next;
    }
    Span* slistEnd(){   // end
        return spanlist_head;
    }
    // 是否为空
    bool isEmpty()
    {
        return spanlist_head->next == spanlist_head;
    }
    // "头删"，只是将被删除的那个Span 给到 threadCache
    Span* popFront()
    {
        Span* front = spanlist_head->next;
        eraseSpanInPos(front);
        return front;
    }
    // 头插
    void pushFront(Span* span)
    {
        insertSpanInPos(slistBegin(), span);
    }
};